package com.kevinkk.string;

/**
 * KMP 算法
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 */

/**
 * 经典的 KMP 算法包含两个部分
 * 第一个部分是求 子串 的 next 数组
 * 第二个部分是用 next 数组进行模式匹配
 */
public class FindTheIndexOfTheFirstOccurrenceInAString {
    class Solution {
        public int strStr(String haystack, String needle) {
            char[] hc = haystack.toCharArray(), nc = needle.toCharArray();
            int[] next = getNext(nc);   // 获取到子串的 next 数组
            int j = 0;                              // j 是子串的指针
            for (int i = 0; i < hc.length; i++) {   // i 是模式串的指针
                // 第一种情况 模式串 和 子串 不同
                while (j > 0 && hc[i] != nc[j])
                    j = next[j - 1];
                // 第二种情况 ... 相同
                if (hc[i] == nc[j])
                    j++;
                // 如果子串遍历完了，那么就算是找到了结果
                if (j == nc.length)
                    return i - j + 1;
            }
            return -1;
        }

        // 求 next 数组
        private int[] getNext(char[] c) {
            int[] next = new int[c.length];
            int j = 0;      // j 指向前缀和的末尾（也表示前缀和的长度）
            next[0] = 0;    // 初始化为 0
            for (int i = 1; i < c.length; i++) {    // i 指向后缀和的末尾
                // 第一种情况 前缀和的末尾 和 后缀和的末尾 不同
                while (j > 0 && c[i] != c[j])
                    j = next[j - 1];                // 不断的向前重新查找
                // 第二种情况 ... 相同
                if (c[i] == c[j])
                    j++;                            // 最长前缀长度增加 1 个
                next[i] = j;
                // 一定得 先判断第一种情况，再判断第二种情况
            }

            return next;
        }
    }
}
